﻿#define _CRT_SECURE_NO_WARNINGS 1
大家都知道 Fibonacci 数列吧，f1 = 1, f2 = 1, f3 = 2, f4 = 3, …, fn = fn−1 + fn−2。

现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Snmodm。

输入格式
共一行，包含两个整数 n 和 m。

输出格式
输出前 n 项和 Snmodm 的值。

数据范围
1≤n≤2000000000,
1≤m≤1000000010
输入样例：
5 1000
输出样例：
12
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef long long ll;

const int N = 3;

int n, m;
ll A[N][N] =    // 上述矩阵 A
{
    {2, 0, -1},
    {1, 0, 0},
    {0, 1, 0}
};
ll S[N] = { 2, 1, 0 }; // 上述矩阵 S（转置）

void multi(ll A[], ll B[][N]) // 计算方阵 B 乘向量 A，并将结果储存在 A 中
{
    ll ans[N] = { 0 };
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            ans[i] += A[j] * B[i][j] % m;
    for (int i = 0; i < N; i++)
        A[i] = ans[i] % m;
}

void multi(ll A[][N], ll B[][N]) // 计算方阵 A * B，并将结果储存在 A 中
{
    ll ans[N][N] = { 0 };
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A[i][j] = ans[i][j] % m;
}

int main()
{
    scanf("%d%d", &n, &m);

    while (n)        // 矩阵快速幂
    {
        if (n & 1) multi(S, A);
        multi(A, A);
        n >>= 1;
    }

    printf("%lld", (S[2] % m + m) % m);

    return 0;
}